package com.codingvip.dynamic;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author Tony.Han
 * @Created at 2020/4/10 8:30 上午
 * Desc:
 */
public class MaxEnvelopes {

    public static void main(String[] args) {
        int[][] envelopes = new int[][]{{2, 100}, {3, 200}, {4, 300}, {5, 500}, {5, 400}, {5, 250}, {6, 370}, {6, 360}, {7, 380}};

//        Arrays.sort(envelopes, (o1, o2) -> {
//            if (o1[0] != o2[0]) {
//                return o1[0] - o2[0];
//            } else {
//                return o1[1] - o2[1];
//            }
//        });
        MaxEnvelopes maxEnvelopes = new MaxEnvelopes();
        int xxxx = maxEnvelopes.maxEnvelopes(envelopes);
        System.out.println(xxxx);
    }

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0) {
            return 0;
        }
        return Math.max(maxEnvelopesMid(envelopes, true), maxEnvelopesMid(envelopes, false));

    }

    private int maxEnvelopesMid(int[][] envelopes, boolean isSortByWidth) {
        if (isSortByWidth) {
            Arrays.sort(envelopes, (int[] b, int[] a) -> {
                if (a[0] == b[0]) {
                    return a[1] - b[1];
                } else {
                    return a[0] - b[0];
                }
            });
        } else {
            Arrays.sort(envelopes, (int[] b, int[] a) -> {
                if (a[1] == b[1]) {
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            });
        }

        int[] dp = new int[envelopes.length];
        dp[0] = 1;
        int[] max = envelopes[0];
        for (int i = 1; i < envelopes.length; i++) {
            if (isSmall(envelopes[i], max)) {
                dp[i] = dp[i - 1] + 1;
                max = envelopes[i];
            } else {
                dp[i] = dp[i - 1];
            }
        }

        return dp[envelopes.length - 1];
    }

    private boolean isSmall(int[] envelope, int[] max) {
        if (envelope[0] >= max[0]) {
            return false;
        }
        if (envelope[1] >= max[1]) {
            return false;
        }
        return true;
    }

//    public int maxEnvelopes(int[][] envelopes) {
//        if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0) {
//            return 0;
//        }
//        Arrays.sort(envelopes, (int[] a, int[] b) -> {
//            if (a[0] == b[0]) {
//                return a[1]-b[1];
//            } else {
//                return a[0] - b[0];
//            }
//        });
//        int[] heights = new int[envelopes.length];
//        for (int i = 0; i < envelopes.length; ++i) {
//            heights[i] = envelopes[i][1];
//        }
//        return lis(heights);
//    }

    private int lis(int[] nums) {
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(nums, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            nums[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}
